1. Field of the Invention
The present invention generally relates to wireless sensor networks, and more particularly to control and routing schemes for such networks.
2. Background Description
In recent years, as the cost of mass produced semiconductor devices has declined, it has become feasible to deploy networks of small devices for sensing fields in the physical world and transmitting sensed data for analysis. These devices can be deployed to provide dense monitoring close to physical phenomena of interest. For example, such sensors can be used to monitor environmental parameters (such as humidity and temperature) or some special events (such as the motion of a target object) in a sensed field. Generally, sensors perform two types of operations: sensing and communicating observed phenomena home. Networked sensors are widely used in various situations, such as monitoring seismic structure response, marine microorganisms, contaminant transport, ecosystems, and battlefields.
Wireless sensor networks, in which each sensor is equipped with a wireless transceiver, are especially useful when infrastructure is unavailable. The recent advances in light-weight operating systems, VLSI technologies, and wireless communications have greatly reduced the size and cost of wireless sensor devices. Therefore, it is possible to deploy large-scale, dense wireless sensor networks to provide environmental monitoring that is suitably dense with respect to both the spatial location and the time of interest.
A wireless sensor network is expected to accomplish sensing, processing, and multi-hop wireless communications. However, the stringent physical constraints involved in designing sensor nodes (i.e., size, cost, and energy) have imposed a severely limited design space on hardware and software complexity, making practical implementation a challenging task. Specifically, for a future sensor node packaged on a cubic-millimeter scale or even smaller, the storage, processing, and communication capabilities on the node will be extremely limited.
The concerns of the prior art argue in favor of doing as much processing and communication as possible at the nodes, on the supposition that each sensor node is capable of executing sophisticated algorithms and protocols. But in reality, when the size of a sensor node goes down to a cubic-millimeter scale, the processing, communication, storage and battery at a sensor node are extremely limited.
Many prior art protocols exploit location information to simplify routing operations. Although these protocols have less computational complexity in routing, they have extra hardware requirements and control overhead on acquiring and distributing location information (e.g., using GPS devices or querying a location database). What is needed is a protocol where location discovery is performed without GPS devices, and without spending energy distributing location information around the network via the sensors, thus allowing simple and low-cost sensor design.
Several sensor routing protocols, such as Low-Energy Adaptive Clustering Hierarchy (LEACH) and GRAdient Broadcast, are designed for large-scale sensor networks. LEACH provides a distributed cluster formation technique, in which sensors elect and rotate cluster heads and form clusters without the involvement of base stations. Therefore, a considerable amount of energy may be spent on maintaining the clusters. Although the centralized cluster scheme, LEACHC, uses base stations for cluster formation, it requires each sensor know its location (e.g., via a GPS device) and transmit its location to the base station. The routing scheme in LEACH requires intelligent sensors with power control capability. Furthermore, the cluster heads communicate directly to the base stations, which is more energy consuming than multi-hop routing. What is needed is a method for forming clusters with minimum processing and communication requirements and costs on sensor nodes, with simple forwarding of data packets through multi-hop relays to a data collection point such as a base station.
In GRAB, a data sink sets up a cost field in the network by broadcasting an advertisement packet to the entire network. Each node, upon receiving the advertisement packet, calculates the minimum cost from itself to the data sink. Then, data packets can be forwarded from higher cost nodes to lower cost nodes, through a mesh with a controllable width lying between the source and the data sink. While GRAB provides an error-resilient method by forwarding data packets through multiple paths, it would be helpful to lower the control overhead (e.g. broadcast advertisements) required by GRAB for wireless sensor networks.
The following characteristics are desirable for control and routing protocols designed for such networks:                Scalability: routing protocols should perform well as the network size grows.        Low complexity: control and routing algorithms should be simple, i.e., with minimum processing, communication, and storage requirements, since sensors generally have very limited capabilities in these areas.        Energy-efficiency: sensors are usually powered by batteries, while recharging is not feasible. In order to extend the lifetime of the sensors (and thus the sensor network's lifetime), the control and routing protocols should be simple and energy efficient.        Error-resilience: wireless sensors are usually deployed in harsh environments (e.g., in the wildness), and are thus exposed to possible damage from, e.g., extreme weather, temperature, pressure, or erosion. In addition, wireless links in a wireless sensor network are fragile and error-prone. Therefore, an error-resilient and robust routing protocol is desirable to ensure successful delivery of data packets.        
In addition, the network topology changes when sensor nodes die or when new sensors are deployed. In this case, the network may need reconfiguration, requiring control and routing protocols that are adjustable in the context of such dynamic re-configurations.